package solution1.demo.demo8;

public class Solution {

//    //1.组合总和 II
//    private List<List<Integer>> res = new ArrayList<>();
//    private List<Integer> list = new ArrayList<>();
//    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//        Arrays.sort(candidates);
//        combinationTrack(candidates, target, 0);
//        return res;
//    }
//
//    private void combinationTrack(int[] candidates, int target, int begin) {
//        if(target == 0) {
//            res.add(new ArrayList<>(list));
//            return;
//        }
//        for(int i = begin; i < candidates.length; i++) {
//            if(i > begin && candidates[i] == candidates[i - 1]) {
//                continue;
//            }
//            if(target - candidates[i] < 0) {
//                continue;
//            }
//            list.add(candidates[i]);
//            combinationTrack(candidates, target - candidates[i], i + 1);
//            list.remove(list.size() - 1);
//        }
//    }

//    //2.复原 IP 地址(回溯)
//    private List<String> res = new ArrayList<>();
//    private List<String> path = new ArrayList<>();
//    public List<String> restoreIpAddresses(String s) {
//        restoreTrack(s, 0);
//        return res;
//    }
//
//    private void restoreTrack(String s, int begin) {
//        if(begin == s.length() && path.size() == 4) {
//            StringBuilder list = new StringBuilder();
//            for(int i = 0; i < 4; i++) {
//                if(i < 3) {
//                    list.append(path.get(i));
//                    list.append(".");
//                } else {
//                    list.append(path.get(i));
//                }
//            }
//            res.add(list.toString());
//            return;
//        } else if(path.size() == 4) {
//            return;
//        }
//        for(int i = begin; i < s.length(); i++) {
//            String val = s.substring(begin, i + 1);
//            int len = val.length();
//            if(!isValue(val, len)) {
//                continue;
//            }
//            path.add(val);
//            restoreTrack(s, i + 1);
//            path.remove(path.size() - 1);
//        }
//    }
//
//    private boolean isValue(String val, int len) {
//        if(len == 1) {
//            return true;
//        }
//        if(len > 3 || Integer.parseInt(val) > 255) {
//            return false;
//        }
//        if(len > 1 && val.charAt(0) == '0') {
//            return false;
//        }
//        return true;
//    }

//    //3.子集 II(回溯)
//    private List<List<Integer>> res = new ArrayList<>();
//    private List<Integer> list = new ArrayList<>();
//    public List<List<Integer>> subsetsWithDup(int[] nums) {
//        Arrays.sort(nums);
//        subsetsTrack(nums, 0);
//        return res;
//    }
//
//    private void subsetsTrack(int[] nums, int begin) {
//        if(begin <= nums.length) {
//            res.add(new ArrayList<>(list));
//        } else {
//            return;
//        }
//        for(int i = begin; i < nums.length; i++) {
//            if(i > begin && nums[i - 1] == nums[i]) {
//                continue;
//            }
//            list.add(nums[i]);
//            subsetsTrack(nums, i + 1);
//            list.remove(list.size() - 1);
//        }
//    }

//    //4.全排列 II(回溯)
//    private List<List<Integer>> res = new ArrayList<>();
//    private List<Integer> list = new ArrayList<>();
//    public List<List<Integer>> permuteUnique(int[] nums) {
//        Arrays.sort(nums);
//        boolean[] path = new boolean[nums.length];
//        permuteTrack(nums, path);
//        return res;
//    }
//
//    private void permuteTrack(int[] nums, boolean[] path) {
//        if(list.size() == nums.length) {
//            res.add(new ArrayList<>(list));
//            return;
//        }
//        HashSet<Integer> set = new HashSet<>();
//        for(int i = 0; i < nums.length; i++) {
//            if(set.contains(nums[i])) {
//                continue;
//            }
//            if(path[i]) {
//                continue;
//            }
//            path[i] = true;
//            set.add(nums[i]);
//            list.add(nums[i]);
//            permuteTrack(nums, path);
//            list.remove(list.size() - 1);
//            path[i] = false;
//        }
//    }

//    //5.n 皇后(回溯 + 模拟)
//    private List<List<String>> res = new ArrayList<>();
//    public List<List<String>> solveNQueens(int n) {
//        //建立棋盘
//        char[][] board = new char[n][n];
//        for(char[] b : board) {
//            Arrays.fill(b, '.');
//        }
//        nQueensTrack(board, n, 0);
//        return res;
//    }
//
//    private void nQueensTrack(char[][] board, int n, int row) {
//        if(row == n) {
//            //转化
//            List<String> list = change(board, n);
//            res.add(new ArrayList<>(list));
//            return;
//        }
//        for(int i = 0; i < n ; i++) {
//            //判断是否可以落子
//            if(isValue(board, n, row, i)) {
//                board[row][i] = 'Q';
//                nQueensTrack(board, n, row + 1);
//                board[row][i] = '.';
//            }
//        }
//    }
//
//    private List<String> change(char[][] board, int n) {
//        List<String> list = new ArrayList<>();
//        for(int i = 0; i < n; i++) {
//            StringBuilder stringBuilder = new StringBuilder();
//            for(int j = 0; j < n; j++) {
//                stringBuilder.append(board[i][j]);
//            }
//            list.add(stringBuilder.toString());
//        }
//        return list;
//    }
//
//    private boolean isValue(char[][] board, int n, int row, int col) {
//        //判断当前列是否可以落子
//        for(int i = 0; i < row; i++) {
//            if(board[i][col] == 'Q') {
//                return false;
//            }
//        }
//        //判断单位圆 45 度角是否有皇后
//        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
//            if(board[i][j] == 'Q') {
//                return false;
//            }
//        }
//        //判断 135 度角
//        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
//            if(board[i][j] == 'Q') {
//                return false;
//            }
//        }
//        return true;
//    }

    //6.爬楼梯(动态规划)
    public int climbStairs(int n) {
        if(n == 1) {
            return 1;
        }
        if(n == 2) {
            return 2;
        }
        //前 i 个楼梯有 n 种方法爬上楼梯
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    //7.使用最小花费爬楼梯(动态规划)
    public int minCostClimbingStairs(int[] cost) {
        //爬上第 i + 1 层楼梯需要的最小费用
        int[] dp = new int[cost.length + 1];
        for(int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }

    //8.不同路径(动态规划)
    public int uniquePaths(int m, int n) {
        //走到 i,j 位置的不同路径
        int[][] dp = new int[m][n];
        //第一行只有一条路径可以走
        for(int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        //第一列只有一条路径可以走
        for(int j = 0; j < m; j++) {
            dp[j][0] = 1;
        }
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    //9.不同路径 II(动态规划)
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //到 i, j 有 dp[i - 1][j - 1] 种不同路径
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        int[][] dp = new int[row][col];
        //第一行
        for(int i = 0; i < col; i++) {
            if(obstacleGrid[0][i] == 1) {
                break;
            }
            dp[0][i] = 1;
        }
        //第一列
        for(int i = 0; i < row; i++) {
            if(obstacleGrid[i][0] == 1) {
                break;
            }
            dp[i][0] = 1;
        }
        for(int i = 1; i < row; i++) {
            for(int j = 1; j < col; j++) {
                if(obstacleGrid[i][j] == 1) {
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[row - 1][col - 1];
    }

    //10.整数拆分(动态规划)
    public int integerBreak(int n) {
        //将 i 拆分成 k 个数的和，使其乘积最大化
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j < i; j++) {
                //这里拆分有两种情况，一种是只拆一次，另一种是拆一次以上
                dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
            }
        }
        return dp[n];
    }



}

class Main {
    public static void main(String[] args) {

    }
}